package com.xjj.tree;

import com.xjj.TreeNode;

public class M0098ValidateBinarySearchTree {

    public boolean isValidBST(TreeNode root) {
        // 左都小于root,右都大于root
        // 左最大的小于root,右最小的大于root
        // 从底向上需要存储很多变量,转换成从顶向下,输入有坑,这里用Long
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode root, long leftMax, long rightMin) {
        if (root == null) {
            return true;
        }
        // 不满足直接归,注意题意这里不能包括等于
        if (root.val <= leftMax || root.val >= rightMin) {
            return false;
        }
        // 左子比root小,右上限为当前root,左下限为历史值,右子同理
        return check(root.left, leftMax, root.val) && check(root.right, root.val, rightMin);
    }

}
